import sys
sys.setrecursionlimit(30000)
def fib(n):
    global cnt
    cnt += 1
    if n == 1 or n == 2:
        data[n] = 1
        return data[n]
    if data[n] != 0:
        return data[n]
    data[n] = fib(n - 1) + fib(n - 2)
    return data[n]

data = [0] * 3005
cnt = 0
print(fib(3000))
print(cnt)